/*
 * @lc app=leetcode.cn id=149 lang=cpp
 * @lcpr version=30204
 *
 * [149] 直线上最多的点数
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 2) return n;   // 如果点数小于等于2，直接返回点数

        int maxCount = 0;       // 记录全局最大共线点数

        // 遍历每个点作为基准点
        for (int i = 0; i < n; ++i) {
            // 哈希表存储斜率与对应点数量的映射
            unordered_map<string, int> slopeCount; // 用于存储斜率的计数
            int duplicate = 1; // 记录与基准点重合的点（至少包含基准点自身）

            // 计算当前点与其他所有点的斜率
            for (int j = i + 1; j < n; ++j) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];

                if (dx == 0 && dy == 0) {
                    // 两点重合，重复点计数加1
                    duplicate++;
                } 
                else {
                    // 计算斜率的最简形式（用最大公约数约分）
                    int gcd = __gcd(dx, dy);
                    dx /= gcd;
                    dy /= gcd;

                    // 统一斜率表示：确保dx为正，避免不同符号表示同一斜率
                    // 例如(2,1)和(-2,-1)是同一斜率，统一为(2,1)
                    if (dx < 0) {
                        dx = -dx;
                        dy = -dy;
                    }

                    // 将斜率转换为字符串作为哈希表的键
                    string slope = to_string(dx) + "/" + to_string(dy);
                    slopeCount[slope]++;
                }
            }

            // 计算当前点的最大共线点数
            int currentMax = 0;
            for (auto& [slope, count] : slopeCount) {
                currentMax = max(currentMax, count);
            }
            
            // 更新全局最大值（当前斜率最大点数 + 重复点数）
            maxCount = max(maxCount, currentMax + duplicate);
        }

        return maxCount;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [[1,1],[2,2],[3,3]]\n
// @lcpr case=end

// @lcpr case=start
// [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]\n
// @lcpr case=end

 */

